package week06

// 63. 不同路径 II
// https://leetcode-cn.com/problems/unique-paths-ii/

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	var m = len(obstacleGrid)
	var n = len(obstacleGrid[0])

	var f = make([][]int, m)
	for i := 0; i < len(f); i++ {
		f[i] = make([]int, n)
	}
	// f[x][y] = f[x][y+1] + f[x+1][y]
	for x := m-1; x >= 0; x-- {
		for y := n-1; y >= 0; y-- {
			if obstacleGrid[x][y] == 1 {
				continue
			}
			if x == m-1 && y == n-1 {
				f[m-1][n-1] = 1
			} else if x == m-1 {
				f[x][y] = f[x][y+1]
			} else if y == n-1 {
				f[x][y] = f[x+1][y]
			} else {
				f[x][y] = f[x][y+1] + f[x+1][y]
			}
		}
	}
	return f[0][0]
}